package org.datacoder.geocoding.datastructures.points

import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.*

class KDTree implements PointsWithinRectangleFinder {

    KDTreeNode root

    public KDTree(Collection<Jurisdiction> jurisdictions){
        List<GeoPoint> geoPoints = new ArrayList<GeoPoint>()
        for(juris in jurisdictions){
            geoPoints.add(juris.toGeoPoint())
        }
        root = createNode(geoPoints)
    }

    public KDTreeNode createNode(List<GeoPoint> geoPoints){
        if(geoPoints.isEmpty()){
            return null
        }

        KDTreeNode kdtNode
        double minLon = 1000
        double maxLon = -1000
        double minLat = 1000
        double maxLat = -1000
        double lonDifference
        double latDifference

        for(gp in geoPoints){
            if(gp.lon < minLon){
                minLon = gp.lon
            }else if(maxLon < gp.lon){
                maxLon = gp.lon
            }
            if(gp.lat < minLat){
                minLat = gp.lat
            }else if(maxLat < gp.lat){
                maxLat = gp.lat
            }
        }

        lonDifference = maxLon - minLon
        latDifference = maxLat - minLat
        int type
        if(lonDifference >= latDifference){
            type = GeoShape.LON
        }else{
            type = GeoShape.LAT
        }


        kdtNode = new KDTreeNode(type)

        Collections.sort(geoPoints, new GeoPointComparator(type))
        int numGeoPoints = geoPoints.size()
        int middle = numGeoPoints/2
        kdtNode.geoPoint = geoPoints.get(middle)

        List<GeoPoint> leftGeoPoints = new ArrayList<GeoPoint>()
        List<GeoPoint> rightGeoPoints = new ArrayList<GeoPoint>()

        for(int i = 0; i < middle; i++){
            leftGeoPoints.add(geoPoints.get(i))
        }
        for(int i = middle + 1; i < numGeoPoints; i++){
            rightGeoPoints.add(geoPoints.get(i))
        }
        kdtNode.left = createNode(leftGeoPoints)
        kdtNode.right = createNode(rightGeoPoints)
        return kdtNode
    }

    public Set<Jurisdiction> findPointsWithinRectangle(GeoRectangle gr){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        Queue<KDTreeNode> kdtNodeQueue = new LinkedList<KDTreeNode>()
        kdtNodeQueue.offer(root)
        while(kdtNodeQueue.peek() != null){
            KDTreeNode currentNode = kdtNodeQueue.poll()
            if(gr.containsGeoPoint(currentNode.geoPoint)){
                jurisdictions.add(currentNode.geoPoint.juris)
            }
            if((currentNode.left != null) && (gr.retrieveMinValue(currentNode.type) <= currentNode.geoPoint.retrieveValue(currentNode.type))){
                kdtNodeQueue.offer(currentNode.left)
            }
            if((currentNode.right != null) && (currentNode.geoPoint.retrieveValue(currentNode.type) <= gr.retrieveMaxValue(currentNode.type))){
                kdtNodeQueue.offer(currentNode.right)
            }
        }
        return jurisdictions
    }
	
}

